package main

import "fmt"

/*
给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

作者：宫水三叶
链接：https://leetcode-cn.com/leetbook/read/path-problems-in-dynamic-programming/rtfiiv/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/

func minimumTotal(triangle [][]int) int {
	minPath := 999
	if len(triangle) == 1 {
		for i := 0; i < len(triangle[0]); i++ {
			if triangle[0][i] < minPath {
				minPath = triangle[0][i]
			}
		}
		return minPath
	}
	var dp [][]int
	for i := 0; i < len(triangle); i++ {
		dp = append(dp, make([]int, len(triangle[i])))
	}
	// base case
	for i := 0; i < len(triangle[0]); i++ {
		dp[0][i] = triangle[0][i]
	}
	for i := 1; i < len(dp); i++ {
		for j := 0; j < len(dp[i]); j++ {
			if j == 0 {
				dp[i][j] = dp[i-1][j] + triangle[i][j]
			} else if j < len(dp[i-1]) {
				dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j]
			} else {
				dp[i][j] = dp[i-1][j-1] + triangle[i][j]
			}
			if i == len(dp)-1 {
				if dp[i][j] < minPath {
					minPath = dp[i][j]
				}
			}
		}
	}
	for i := 0; i < len(dp); i++ {
		fmt.Println(dp[i])
	}
	return minPath
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	triangle := [][]int{
		{2},
		{3, 4},
		{6, 5, 7},
		{4, 1, 8, 3},
	}
	// triangle := [][]int{{-10}}
	fmt.Println(minimumTotal(triangle))
}
